package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;

/**
 * 最大子数组和 ，可能与 {@link com.zk.algorithm.array.GreatestSumOfSubArray} 重复
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class MaximumSubarray {

    public int maxSubArray(int[] A) {
        return maxSubArray(A, 0, A.length - 1);
    }

    public int maxSubArray(int[] A, int low, int high) {
        if (low == high) {
            return A[low]; //if only one element, return that
        }

        int mid = low + (high - low) / 2;
        int leftMaxSum = maxSubArray(A, low, mid);
        int rightMaxSum = maxSubArray(A, mid + 1, high);

        // lets calculate the part in which sub array will start in the left half and ends in right half
        int sum = 0;

        // ===================
        // 左最大值
        // [0,1,2,3,4,5,6]
        //        ↑(mid)
        //       ←
        //      ←
        //     ←
        //    ←
        // ===================
        //
        // 如果这个地方 leftMidMax = 0 的话，那么数组全是负数的情况下，可能会返回错误结果
        int leftMidMax = Integer.MIN_VALUE;
        for (int i = mid; i >= low; i--) {
            sum += A[i];
            if (sum > leftMidMax)
                leftMidMax = sum;
        }

        // ===================
        // 右最大值
        // [0,1,2,3,4,5,6]
        //        ↑(mid)
        //         →
        //          →
        //           →
        //            →
        // ===================
        sum = 0;
        // 如果这个地方 rightMidMax = 0 的话，那么数组全是负数的情况下，可能会返回错误结果
        int rightMidMax = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= high; i++) {
            sum += A[i];
            if (sum > rightMidMax)
                rightMidMax = sum;
        }

        // ===================
        // 跨越中间的最大值
        // ===================
        int centerSum = leftMidMax + rightMidMax;

        // ===================
        // 三者取最大的
        // ===================
        return Math.max(centerSum, Math.max(leftMaxSum, rightMaxSum));
    }

    public static int maxSubArrayDP(int[] A) {
        int maxSoFar = A[0], maxEndingHere = A[0];

        for (int i = 1; i < A.length; ++i) {
            // 贡献度: A[i]
            maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }

}
